package com.bwt.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class InsertSort {
    public static void main(String[] args) {

  /*      int arr[] = {101, 34, 119, 1};
        insertSort(arr);*/


        //测试一下插入排序的速度:O(n^2),给80000个的数据,测试
        int[] arr = new int[80000];
        for(int i = 0;i < 80000;i++){
            arr[i] = (int)(Math.random() * 80000);	//自动生成[0,80000)之间的随机数
        }

        //排序前的时间:
        Date data = new Date();
        SimpleDateFormat simt = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String dateS = simt.format(data);
        System.out.println("排序前的时间是:" + dateS);	//2020-05-29 11:31:53

        insertSort(arr);	//调用插入排序

        //排序后的时间:
        Date data2 = new Date();
        SimpleDateFormat simt2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String dateS2 = simt2.format(data2);
        System.out.println("排序后的时间是:" + dateS2);
        /*排序前的时间是:2022-07-10 19:45:24
        排序后的时间是:2022-07-10 19:45:28*/
    }

    public static void insertSort(int[] arr) {

        int insertValue = 0;
        int insertIndex = 0;

        //使用for循环
        for (int i =1; i < arr.length; i++) {
             insertValue = arr[i];
             insertIndex = i - 1; // 即arr[1] 前面的这个下标

            while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }

            if (insertIndex + 1 == i) {
                arr[insertIndex + 1] = insertValue;
            }
            //System.out.println("第"+i +"轮插入后, 数组:" + Arrays.toString(arr));
        }

      /*  //使用逐步推到的过程

        //第1轮{101, 34, 119, 1}; =》 {34, 101, 119, 1};

        //定义待插入的数
        int insertValue = arr[1];
        int insertIndex = 1 - 1; // 即arr[1] 前面的这个下标

        // 给insertval 找到插入的位置
        //insertIndex >= 0 保证 再给insertValue找插入位置时, 不越界
        // insertValue< arr[insertIndex]  待插入的数, 还没有找到插入的位置
        while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
            arr[insertIndex + 1] = arr[insertIndex];
            insertIndex--;
        }
        // 当退出while 循环时, 说明插入的位置找到 insertIndex +1
        arr[insertIndex + 1] = insertValue;

        System.out.println("第一轮插入后, 数组:" + Arrays.toString(arr));

        insertValue = arr[2];
        insertIndex = 2 - 1;

        while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
            arr[insertIndex + 1] = arr[insertIndex];
            insertIndex--;
        }
        arr[insertIndex + 1] = insertValue;

        System.out.println("第二轮插入后, 数组:" + Arrays.toString(arr));

        insertValue = arr[3];
        insertIndex = 3 - 1;

        while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
            arr[insertIndex + 1] = arr[insertIndex];
            insertIndex--;
        }
        arr[insertIndex + 1] = insertValue;
        System.out.println("第三轮插入后, 数组:" + Arrays.toString(arr));*/
    }
}
